package com.fengye.algorithms.leecode.dp;

/**
 * @Author fengye
 * @Date 2023/4/27 8:18
 **/
public class DistinctSubsequences115 {
    public static void main(String[] args) {
        System.out.println(new DistinctSubsequences115().numDistinct2("rabbbit", "rabbit"));
    }

    public int numDistinct2(String s, String t) {
        if(s.isEmpty()||t.isEmpty()){
            return 0;
        }
        int tLen=t.length();
        int sLen=s.length();
        char[] chars=t.toCharArray();
        int[] mat=new int[tLen+1];
        for (int j = 0; j < sLen; j++) {
            char c=s.charAt(j);
            int start=Math.max(tLen-sLen+j,0);
            for(int i=Math.min(j+1,tLen);i>start;i--){
                if(chars[i-1]==c){
                    if(i==1){
                        mat[i]+=1;
                    }else {
                        mat[i]+=mat[i-1];
                    }
                }
            }
        }
        return mat[tLen];
    }

    public int numDistinct(String s, String t) {
        int sLen = s.length();
        int tLen = t.length();

        int[][] dp = new int[tLen + 1][sLen + 1];

        // 边界条件，“ ”空串也是子串
        for(int i = 0; i <= sLen; i++) {
            dp[0][i] = 1;
        }

        for(int i=1;i<=tLen;i++) {
            for(int j=1;j<=sLen;j++) {
                // 如果字符串t的第i个字符和s的的j个字符一样
                if(t.charAt(i-1) == s.charAt(j-1)) {
                    // 有两种选择
                    // 1、用字符串s的第j个字符和t的第i个字符匹配,即rabbbi中包含多少个rabbi
                    // 2、不用s的第j个字符和t的第i个字符匹配,即rabbbi中包含多少个rabbit
                    dp[i][j] = dp[i-1][j-1] + dp[i][j-1];
                } else {
                    dp[i][j] = dp[i][j-1];
                }
            }
        }
        return dp[tLen][sLen];
    }
}
